/**
 * 项目名称: Topic_235.cpp
 * 项目路径: study/DataStructure/LeetCode/树/中等
 * 编辑时间: 2024年08月28日07时22分16秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<TreeNode *> Ino(TreeNode *root, TreeNode *p) {
        vector<TreeNode *> path;
        TreeNode *node = root;
        while (node != p) {
            path.push_back(node);
            if (p->val > node->val)node = node->right;
            else if(p->val < node->val) node = node->left;
        }
        path.push_back(node);
        return path;
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (!root)return nullptr;
        vector<TreeNode *> ve = Ino(root, p);
        vector<TreeNode *> vn = Ino(root, q);
        TreeNode *ans;
        for (int i = 0; i < ve.size() && i < vn.size(); i++) {
            if (ve[i] == vn[i])ans = ve[i];
            else break;
        }
        return ans;
    }
};
